The necessity of adapting higher layer packets to the characteristics of a physical network is a classical issue for all type of communication systems, such as wireless networks (GSM, UMTS, WiLAN, WiMax etc.) or fixed networks (IP, Frame relay, PPP, ATM, etc).
General Overview of the OSI Layer
In this section, a brief introduction is given to the OSI model (see FIG. 1) that will be used to illustrate the explanations below.
The Open Systems Interconnection Reference Model (OSI Model or OSI Reference Model for short) is a layered abstract description for communications and computer network protocol design. The OSI model divides the functions of a system into a series of layers. Each layer has the property that it only uses the functions of the layer below, and only exports functionality to the layer above. A system that implements protocol behavior consisting of a series of these layers is known as a ‘protocol stack’ or ‘stack’. Its main feature is in the junction between layers which dictates the specifications on how one layer interacts with another. This means that, in principle, a layer written by one manufacturer can operate with a layer from another. For our purpose, only the three first layers will be described.
The main purpose of the physical layer, or layer 1 is the transfer of information (bit) over a specific physical medium (e.g. coaxial cables, twisted pairs, optical fibers or the air). It converts or modulates data into signals that are transmitted over a communication channel.
The purpose of the data link layer, or layer 2 is to shape the information flow in a way compatible with the specific physical layer by breaking up the input data into data frames (Segmentation And Re-assembly or SAR functions). Furthermore it may detect and correct potential transmission errors by requesting a retransmission of a lost frame. It provides an addressing mechanism and may offer flow control algorithms in order to align the data rate with the receiver capacity. Finally, when a shared medium is concurrently used by multiple transmitter and receivers, it offers mechanisms to regulate and control access to the physical medium. As the span of functions of the data link layer is large, the data link layer is often subdivided in two sublayers (e.g. RLC and MAC sublayers in UMTS). Typical examples of layer 2 protocols are PPP/HDLC, ATM, frame relay for fixed line networks and RLC, LLC or MAC for wireless systems.
The network layer, or layer 3 provides the functional and procedural means for transferring variable length packets from a source to a destination via one or more networks while maintaining the quality of service requested by the transport layer. The main purposes of the network layer are to perform network routing, network fragmentation and congestion control functions. The main examples of network layer protocols are the IP Internet Protocol or X.25.
More information on OSI layer model can be found in “Computer Networks”, (Andrew S. Tanenbaum, fourth edition, Prentice Hall International Edition, page 37-41, section 1.4.).
SDU and PDU Definition
In order to formally describe in a generic way the exchange of packets between layers in the OSI model, SDU (Service Data Unit) and PDU (Protocol Data Unit) entities have been defined. An SDU is a unit of information transmitted from a protocol at the layer N+1 that requests a service to a protocol located at layer N via an SAP (Service Access Point). A PDU is a unit of information exchanged between peer processes at the transmitter and at the receiver of the same protocol located at the same layer N. A PDU is generally formed by a payload part consisting of the processed version of the received SDU and control information, e.g. a layer N specific header and possibly terminated by a trailer. Since there is no direct physical connection (except for L1) between these peer processes, a PDU is forwarded to the layer N−1 for processing. Therefore a layer N PDU is from a layer N−1 point of view a SDU. This is illustrated in FIG. 2.
Purpose of Fragmentation/Segmentation
Fragmentation, or equivalently segmentation, may be required for three different reasons.
First of all, fragmentation may be required to transport datagrams or packets though networks whose maximum allowed datagram size or maximum transfer unit (MTU) is smaller than their size. Datagram fragmentation is typically implemented at the IP layer and is specified as the IP Fragmentation in the IPv4 or IPv6 version of the standard. Similarly segmentation is necessary when data is transported over an ATM network in order to fit a payload size of 48 octets into the ATM cell. This is performed in the ATM adaptation layers (AAL) between the ATM layer 2 and the transport layer (e.g. IP).
Secondly, fragmentation may be carried out in order to balance traffic load on parallel links for instance on parallel ISDN links. The PPP multilink protocol (MP) (“The PPP Multilink Protocol (MP)”, RFC 1990, Sklower, K., Lloyd, B., McGregor, G., Carr, D. and T. Coradetti, August 1996) based on PPP describes a method for splitting, recombining and sequencing datagrams across multiple logical data links.
Finally, in wireless systems, packet segmentation potentially combined with concatenation is often performed at the layer 2 (e.g in RLC sublayer in UMTS, 3GPP TS 25.322, v6.4.0, “Radio Link Control (RLC) protocol specification”) in order to fit higher layer packets into the resources offered by the lower layer. As resources are typically scarce in a wireless environment, concatenation of several higher layer packets is recommended in order to enhance the overall system efficiency.
In order for the receiver unit to separate concatenated fragments and correctly recombine the received fragments into the original packets, segmentation information needs to be delivered to the receiving unit. This information, usually combined with a numbering technique tagging each fragment, enables the layer 2 at the receiver to deliver full and consistent packets to the next higher layer.
In the following sections, several existing methods to signal segmentation will be presented which will help to understand the differences to the present invention.
SAR Signaling Via Fragment Numbering
The first class of methods to indicate fragmentation regroups several similar techniques that indicate the position of the fragments within the source packet. Two elements are necessary: the first one is an index pointing to the position of the fragment within the source packet. This index can either take the form of a fragmentation offset (IP fragmentation, see “Computer Network”, Andrew S. Tanenbaum, fourth edition, Prentice Hall International Edition, page 37-41 section 1.4.) or equivalently a fragment sequence number FSN (WiLAN, see 802.11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) specifications).
This index must be initialized to a known value (e.g. FSN=zero) for the first fragment of a source packet. The receiver unit uses this index to record fragments in the correct sequence and detect lost fragments. Furthermore the last fragment of a packet is indicated with a one-bit flag (LF). An un-fragmented packet is signaled to the receiver side by setting the index to the initial position (e.g. FSN=zero) and simultaneously indicating that this packet is a last fragment in the source packet. This technique is used for instance in IP fragmentation protocol or in the ATM Adaptation Layer AAL-1. The 802.11 WiLAN MAC layer uses the same technique as well. WiLAN also appends a field identifying the source packet to each fragment. This is necessary as 802.11 MAC may be configured to re-order packets at the receiver side before delivery to the next higher layer. This in-sequence delivery requirement does not exist at the IP layer, as reordering is either not required or performed by a higher layer (e.g. TCP).
The principle of the SAR technique via fragment numbering in WiLAN is shown in FIG. 3.
The signaling overhead is relatively significant since each fragment must carry at least the last fragment flag LF and the fragment sequence number FSN and eventually the sequence number SN of the source packet.
SAR Signaling Via Beginning/End Flags
The second class of SAR methods is widely used in various protocols such as ATM Adaptation layer AAL-3/4, Frame Relay Frame Relay Fragmentation Implementation Agreement FRF.12, Frame Relay Forum Technical Committee, WiMax and PPP multilink (MP) (“The PPP Multilink Protocol (MP)”, RFC 1990, Sklower, K., Lloyd, B., McGregor, G., Carr, D. and T. Coradetti, August 1996). The main idea in this second class of SAR techniques is to use two one-bit flags to indicate for each SAR PDU, whether the PDU is the first, the last or a middle fragment of an SDU or whether it is a complete SAR SDU. Both flags are part of the PDU header. In some implementations (Frame Relay and PPP multilink), one distinguishes the function of the two flags as one indicating the beginning of an SDU and the other one indicating its end. The beginning fragment bit B is set to 1 on the first fragment derived from an SAR SDU and set to 0 for all other fragments from the same SDU. The ending fragment bit E is set to 1 on the last fragment and set to 0 for all other fragments. A PDU may have both the beginning and ending fragment bits set to 1. In this case, it indicates that no segmentation took place. A fragment sequence numbering is further added in order to the receiver unit to detect fragment loss and potentially to perform PDU reordering if the link does not preserve the PDU sequence. After reordering, the receiver can easily check the B and E bits to identify which SAR PDU need to be combined to re-build the original SDUs. Figure gives an illustration of this technique.
SAR Signaling Via Length Indicators
A third class consists in a set of techniques that are using length indicator fields as pointers to indicate the boundaries of the SDUs. A good example is the RLC (Radio Link Control) in UMTS R99. In RLC, an RLC PDU may carry segments of several SDUs or padding bits. Indeed UMTS R99 operates with fixed size PDU which may not be aligned with the length of the SDUs to be transmitted. As radio resources are scarce, it was seen as necessary to allow concatenation of SDU at PDU level. In a generic way, a variable number of length indicators (LI) are added to the PDU header. A length indicator is used to indicate the last octet of each RLC SDU ending within the PDU. As usual, a sequence numbering based on the PDU is added in the header in order to enable loss detection and reordering. The receiver can therefore perform reordering, request the retransmission of lost PDU and re-assemble the SDU. Furthermore an LI with a special value indicates when padding is used to fill up the end of a PDU.
The main drawback of this technique is that the overhead depends on the number of SDU segments in a PDU, and due to this the header also has a variable size. Moreover the usage of special fields tends to raise the complexity of the RLC.
Finally, this technique is not very efficient when considering variable PDU size, which would be more flexible and better adapted to a full packet oriented environment over a wireless system. A generic example of this technique is shown in FIG. 5.
Concatenation Function in Wireless System
Concatenation is a function that is particularly useful for wireless systems. The combination of segmentation and concatenation enables the transmitter to adapt the incoming, variable length SDUs better to the resources offered. In case of wireless system, the number of bits that can be transmitted over a transmission time interval (TTI) may significantly vary depending on the radio conditions, the code rate and the physical resources dedicated to the transmission. For instance, a mobile station close to the transmitter requires less channel encoding than a mobile station further away. With the same allocated physical resources and the same transmission power, the first mobile station will be able to receive much more data than the second mobile station. Moreover, when packet services are considered, the data rate provided by the server may in principle vary significantly over time.
In UMTS, SDU segmentation and concatenation of SDU segments into PDU are performed at the RLC level without respect to the physical resources offered and with fixed pre-defined PDU size. In order to emulate some kind of dynamic behavior, the MAC layer, based on some indications from the physical layer, determines the number of PDUs to be transmitted per TTI. In UMTS R99, the selected PDUs are transmitted in the form of so-called transport channel blocks (TrCH Blk or TrBlk) to the physical layer which concatenates them and forms a transport channel block set. In UMTS Rel-5 HSDPA, the selected PDUs are directly concatenated in the MAC layer transport channel block (TrCH Blk or TrBlk) which, thus, contains several PDUs as shown in FIG. 6. Depending on the radio conditions or other variables, the number of selected PDUs per TTI varies as shown in FIG. 7. Therefore the sequential use of SDU segmentation/concatenation at the RLC layer with PDU concatenation at the MAC layer (UMTS Rel-5 HSDPA) or at the physical layer (UMTS R99) enables the transmitter to dynamically adapt the transmission to instantaneous variables (incoming data from upper layer and resources offered by lower layers).
In UMTS, the receiver unit is informed of the number of PDUs transmitted per TTI either via out-of-band signaling (Transport Format Combination Indicator or TFCI) or in-band in a specific header (e.g. MAC-hs header in HSDPA). It should be noted that the PDU concatenation step is generally performed independently of the structure of the PDUs, thus it may happen that a SDU spans over several TTIs.
Efficient Overhead in Systems with Highly Variable Data Rate
The sequential use of SDU segmentation and PDU concatenation as presented above works well when the range of the number of PDUs to be transmitted is not too large. However in case of highly variable systems (highly variable physical resources and highly variable data rate), which may become more common in future systems with high bandwidth, the usage of a fixed size PDU tends to be suboptimum as the size of the PDU may not be adapted to the full range of the data rate. Indeed in the case of packet service the size of the SDU can in principle vary from 40 octets for TCP acknowledgements up to the size of the MTU (e.g. around 1500 octets for Ethernet). On the physical layer side, scheduled shared systems such as HSDPA in UMTS offer physical resources per TTI that may vary from few kbps to the complete bandwidth (e.g. 14 Mbps in HSDPA). It is expected that this trend will be confirmed by future wireless system.
The problem comes from the fact that the small PDU size that would be optimal for the lower part of the data rate span, becomes a burden when considering the higher part of the data rate span. Indeed, the receiver will have more PDUs to treat per TTI and would require more computation. Furthermore the sequence number range identifying the PDUs may become too short, and a wrap around problem may occur. Finally the overhead, which is equal to n*PDU header_size, increases more or less linearly with the length of the transport channel block. Using a large PDU will force the transmitter to either delay transmission in order to fill up the PDU or to heavily pad the unused space in the PDU at low data rates. Increased jitter or extensive padding have a strong negative influence on the efficiency of a radio system and should be avoided.
In general, the size of the PDU is a static parameter of the radio bearer used to carry the considered service. This parameter cannot be changed without a heavy reconfiguration procedure. Therefore it is difficult to efficiently adapt the link to the characteristics of the incoming SDUs or to the resources offered by the lower layer without strong limitations on either the data rate or the range of physical resources that can be allocated per TTI.
Error Propagation
The SAR signaling techniques with length indicators are sensitive to error propagation. Indeed it may happen that the loss of a PDU forces the receiver to intentionally drop correctly received SDUs due to SDU border uncertainty. As shown in FIG. 8, the loss of PDU i+2 forces the receiver to drop the correctly received PDU i+3, since it cannot determine whether the fragment contained in PDU i+3 is a full SDU (alternative 1) or a segment of SDU (alternative 2).
In UMTS Rel-6, some attempts have been made to limit this issue and to reduce the overhead in some particular conditions where the SDU size matches the PDU size. However in the general case, this problem comes from the fact that each PDU carries information on its own structure and without respect to the inner structure of the adjacent PDUs.
SAR signaling techniques with beginning/end flags or with fragment numbering are much more robust in this as the receiver exactly knows when enough PDUs are received. However, the overhead of these techniques increases linearly with the number of concatenated PDUs.
As can be seen, several techniques exist to signal segmentation and concatenation. However they tend to suffer either from high overhead, lack of flexibility or may lead to increased complexity at the receiver side. Robustness towards error propagation is not given, either.